/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package busquedaProfundidad;
import gui.ExcepcionParada;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JOptionPane;

/**
 * Nota: En todos los lugares donde aparesca la sentencia System.out.println()
 * es solo para fines de obtener retroalimentacion en el programa de sobre que
 * esta haciendo como para saber durante el desarrollo del mismo si es que hace
 * efectivamente lo planteado
 */
public class busquedaProfundidad {
    /* ESTA CLASE REALIZA LA BUSQUEDA EN PROFUNDIDAD*/
    public boolean parar = false;
    Nodo estadoInicial;
    public List<Nodo> camino;
    public List<Nodo> explorados;
    //Parametros para la comparacion, que seran devueltos como resultados de la busqueda
    public int profundidadMaxima;
    public int resguardoExploracion;
    public int cantidadNodosGenerados;
    public int nivelSolucion;
    public boolean encontroSolucion;
    public long tiempoTotalBusqueda;
    boolean banderaDeMsjDeExcepcion = false;
    public int costoFinal;
    int nivelTope = 0;
    boolean activoNivelTope = false; //Indica si el usuario eligio para la busqueda en un nivel dado
    //Constructor de la clase
    public busquedaProfundidad(Nodo recibido, int nivelTopeR){
       estadoInicial = new Nodo(recibido.getPosicion());
       estadoInicial.setCosto(recibido.getCosto());
       estadoInicial.setAcum20(recibido.getAcum20());
       camino = new ArrayList();
       explorados = new ArrayList();
       //
       profundidadMaxima = 0;
       resguardoExploracion = 0;
       cantidadNodosGenerados = 0;
       nivelSolucion = 0;
       encontroSolucion = false;
       tiempoTotalBusqueda = 0;
       costoFinal = 0;
       if(nivelTopeR==0){

       }else{
           this.nivelTope = nivelTopeR;
           this.activoNivelTope = true;
           //La busqueda parara en el nivelTope
       }

    }

     //Metodo que efectivamente realiza la busqueda
    public void buscarEnProfundidad() throws ExcepcionParada{

        //Aca comenzamos a contar el tiempo
        long tiempoInicio = System.currentTimeMillis();
        long totalTiempo = 0;
        camino.add(estadoInicial);
        boolean nollegoAlFinal = true;
        if(this.esEstadoFinal(this.getEstadoInicial())){
                nollegoAlFinal = false;
                this.nivelSolucion = this.profundidadMaxima;
                this.encontroSolucion = true;
        }
        int reglaAplicada = 1;
        int cantNivelesRecorridos = 0;

        if(this.activoNivelTope){
            //BUSQUEDA HASTA EL NIVEL INDICADO

            while((nollegoAlFinal)&&(cantNivelesRecorridos<this.nivelTope)){

                    int ultimoELM;
                    ultimoELM = this.camino.size() - 1;

                    Nodo estadoActual;
                    estadoActual = this.camino.get(ultimoELM);
                    Sucesor tenerHijo = new Sucesor(estadoActual);

                    // OBTIENE EL SUCESOR APLICANDO LA PRIMERA REGLA QUE PUEDE
                    reglaAplicada = tenerHijo.obtenerHijo(reglaAplicada);

                    Nodo hijo;
                    int ultimoHIJO;
                    ultimoHIJO = tenerHijo.getHijos().size() - 1;
                    hijo = tenerHijo.getHijos().get(ultimoHIJO);
                    this.cantidadNodosGenerados = this.cantidadNodosGenerados + 1;

                    //CONTROLES A LOS SUCESORES

                    //SE VERIFICA QUE EL CABALLO NEGRO NO VUELVA A UNA POSICION REPETIDA
                    boolean noRepitioPosicion = true;
                    int k = this.camino.size() - 1;
                    while((noRepitioPosicion)&&(k>=0)){

                        Nodo elm;
                        elm = this.camino.get(k);
                        int filaCNA;
                        int colCNA;
                        filaCNA = elm.filaCN();
                        colCNA = elm.colCN();
                        int filaCNHijo;
                        int colCNHijo;
                        filaCNHijo = hijo.filaCN();
                        colCNHijo = hijo.colCN();

                        if((filaCNA == filaCNHijo)&&(colCNA == colCNHijo)){
                            noRepitioPosicion = false;
                            reglaAplicada = reglaAplicada + 1;
                            reglaAplicada = tenerHijo.obtenerHijo(reglaAplicada);
                            ultimoHIJO = tenerHijo.getHijos().size() - 1;
                            hijo = tenerHijo.getHijos().get(ultimoHIJO);

                        }

                        k = k - 1;
                    }


                   //SE VERIFICA QUE NO ESTE EN LISTA DE EXPLORADOS
                   boolean noRepetido = true;
                   int p = this.explorados.size() - 1;
                   while((noRepetido)&&(p>=0)){
                       int [][] elmCerrados = this.explorados.get(p).getPosicion();
                       ultimoHIJO = tenerHijo.getHijos().size() - 1;
                       int [][] matrizHijo = tenerHijo.getHijos().get(ultimoHIJO).getPosicion();

                       boolean igual = true;
                       for(int i=0;i<8;i++){
                           for(int j=0;j<8;j++){
                              if(elmCerrados[i][j] != matrizHijo[i][j]){
                                igual = false;
                              }
                           }
                       }

                      if(igual){
                        //Esto se hace solo a fines de evitar errores al aplicar la regla
                        if(reglaAplicada == 8){
                            reglaAplicada = 1;
                        }else{
                            reglaAplicada = reglaAplicada + 1;
                        }

                        reglaAplicada = tenerHijo.obtenerHijo(reglaAplicada);
                        System.out.println("Encontro un hijo en cerrados, generamos uno nuevo");

                      }else{
                           p = p - 1;
                      }
                   }

                    ultimoHIJO = tenerHijo.getHijos().size() - 1;
                    hijo = tenerHijo.getHijos().get(ultimoHIJO);

                    //VERIFICAMOS QUE NO ESTE REPETIDO EN LA RAMA EXPLORADA
                   boolean noRepetidoA = true;
                   int p1 = this.camino.size() - 1;
                   while((noRepetidoA)&&(p1>=0)){

                       int [][] elmAbiertos = this.camino.get(p1).getPosicion();
                       ultimoHIJO = tenerHijo.getHijos().size() - 1;
                       int [][] matrizHijo = tenerHijo.getHijos().get(ultimoHIJO).getPosicion();

                       boolean igual = true;
                       for(int i=0;i<8;i++){
                           for(int j=0;j<8;j++){
                              if(elmAbiertos[i][j] != matrizHijo[i][j]){
                                igual = false;
                              }
                           }
                       }

                      if(igual){

                        if(reglaAplicada == 8){
                            reglaAplicada = 1;
                        }else{
                            reglaAplicada = reglaAplicada + 1;
                        }

                        reglaAplicada = tenerHijo.obtenerHijo(reglaAplicada);
                        System.out.println("Encontro un hijo en abiertos, generamos uno nuevo");

                      }else{
                           p1 = p1 - 1;
                      }

                   }

                   //EL NUEVO NODO ES VALIDO, NO ES REPETIDO NI RESPONDE A POSICIONES ANTERIORES

                    ultimoHIJO = tenerHijo.getHijos().size() - 1;
                    int valorDelAcum;
                    valorDelAcum = tenerHijo.getHijos().get(ultimoHIJO).getAcum20();

                    //VERIFICAMOS SI SE TRATA DE UNA RAMA INUTIL
                    if(valorDelAcum>=30){
                        //debemos podar la rama
                        Nodo podado;
                        podado = tenerHijo.getHijos().get(ultimoHIJO);
                        this.explorados.add(podado);
                        System.out.println("Se agrego un nodo en explrados xq pasamos el 30");
                        if(reglaAplicada == 8){
                                reglaAplicada = 1;
                         }else{
                                reglaAplicada = reglaAplicada + 1;
                         }

                         reglaAplicada = tenerHijo.obtenerHijo(reglaAplicada);

                         ultimoHIJO = tenerHijo.getHijos().size() - 1;
                         tenerHijo.getHijos().get(ultimoHIJO).setAcum20(0);

                         //Aca hizo backtraking entonces resguardamos la profundidad alcanzada
                         this.resguardoExploracion = this.getProfundidadMaxima();
                         this.profundidadMaxima = this.profundidadMaxima - 1;
                         //

                    }
                    ultimoHIJO = tenerHijo.getHijos().size() - 1;
                    Nodo hijoNoRepetido;
                    hijoNoRepetido = tenerHijo.getHijos().get(ultimoHIJO);
                    hijoNoRepetido.setCosto(tenerHijo.getHijos().get(ultimoHIJO).getCosto());
                    hijoNoRepetido.setAcum20(tenerHijo.getHijos().get(ultimoHIJO).getAcum20());
                    this.camino.add(hijoNoRepetido);
                    //SE AGREGA EL NUEVO NODO A ABIERTOS PORQUE CUMPLIO CON TODAS LAS CONDICIONES

                    cantNivelesRecorridos = cantNivelesRecorridos + 1;
                    this.costoFinal = hijoNoRepetido.getCosto();

                    //Incrementamos el contador de produndidad
                    this.profundidadMaxima = this.profundidadMaxima + 1;
                    if(this.profundidadMaxima>this.resguardoExploracion){

                        this.resguardoExploracion = this.profundidadMaxima;
                    }

                    System.out.println("REGLA APLICADA:"+reglaAplicada);

                    if(this.esEstadoFinal(hijoNoRepetido)){
                        nollegoAlFinal = false;
                        this.nivelSolucion = this.profundidadMaxima;
                        this.encontroSolucion = true;
                    }
                    reglaAplicada = 1;

                    System.out.println("Hijo obtenido");
                    hijoNoRepetido.mostrarValores();

                    //Aca recalculamos el tiempo
                    totalTiempo = System.currentTimeMillis() - tiempoInicio;
                    this.setTiempoTotalBusqueda(totalTiempo);

                    //VERIFICAMOS SI HAY QUE PARAR POR DECISION DEL USUARIO
                    if(this.parar){
                        nollegoAlFinal = false;
                        JOptionPane.showMessageDialog(null, "La Búsqueda ha sido detenida por decisión del usuario");
                        throw new ExcepcionParada("La busqueda ha sido detenida por el usuario");


                    }

                    //Esto se hace porque es necesario para cumplir la condicion del while
                    if(this.esEstadoFinal(hijoNoRepetido)){
                        nollegoAlFinal = false;
                        totalTiempo = 90000;
                        this.nivelSolucion = this.profundidadMaxima;
                        this.encontroSolucion = true;
                    }
                }
                 //SE HACE POR CONTROLAR NO MAS
                 if(nollegoAlFinal){
                     this.encontroSolucion = false;
                 }

        }else{

        //BUSQUEDA SIN TOPE DE NIVEL
            while((nollegoAlFinal)){

                int ultimoELM;
                ultimoELM = this.camino.size() - 1;
                Nodo estadoActual;
                estadoActual = this.camino.get(ultimoELM);
                Sucesor tenerHijo = new Sucesor(estadoActual);

                // OBTIENE EL SUCESOR APLICANDO LA REGLA QUE PUEDE
                reglaAplicada = tenerHijo.obtenerHijo(reglaAplicada);
                Nodo hijo;
                int ultimoHIJO;
                ultimoHIJO = tenerHijo.getHijos().size() - 1;
                hijo = tenerHijo.getHijos().get(ultimoHIJO);
                this.cantidadNodosGenerados = this.cantidadNodosGenerados + 1;

                //CONTROL DE POSICIONES REPETIDAS
                boolean noRepitioPosicion = true;
                int k = this.camino.size() - 1;
                while((noRepitioPosicion)&&(k>=0)){

                    Nodo elm;
                    elm = this.camino.get(k);
                    int filaCNA;
                    int colCNA;
                    filaCNA = elm.filaCN();
                    colCNA = elm.colCN();

                    int filaCNHijo;
                    int colCNHijo;
                    filaCNHijo = hijo.filaCN();
                    colCNHijo = hijo.colCN();

                    if((filaCNA == filaCNHijo)&&(colCNA == colCNHijo)){
                        noRepitioPosicion = false;
                        reglaAplicada = reglaAplicada + 1;
                        reglaAplicada = tenerHijo.obtenerHijo(reglaAplicada);
                        ultimoHIJO = tenerHijo.getHijos().size() - 1;
                        hijo = tenerHijo.getHijos().get(ultimoHIJO);

                    }

                    k = k - 1;

                }

               //CONTROL DE SI ESTA O NO EN EXPLORADOS
               boolean noRepetido = true;
               int p = this.explorados.size() - 1;
               while((noRepetido)&&(p>=0)){

                   int [][] elmCerrados = this.explorados.get(p).getPosicion();
                   ultimoHIJO = tenerHijo.getHijos().size() - 1;
                   int [][] matrizHijo = tenerHijo.getHijos().get(ultimoHIJO).getPosicion();

                   boolean igual = true;
                   for(int i=0;i<8;i++){
                       for(int j=0;j<8;j++){
                          if(elmCerrados[i][j] != matrizHijo[i][j]){
                            igual = false;
                          }
                       }
                   }

                  if(igual){

                    if(reglaAplicada == 8){
                        reglaAplicada = 1;
                    }else{
                        reglaAplicada = reglaAplicada + 1;
                    }

                    reglaAplicada = tenerHijo.obtenerHijo(reglaAplicada);
                    System.out.println("Encontro un hijo en cerrados, generamos uno nuevo");
                    //p = this.cerrados.size() - 1;
                  }else{
                       p = p - 1;
                  }

               }

                ultimoHIJO = tenerHijo.getHijos().size() - 1;
                hijo = tenerHijo.getHijos().get(ultimoHIJO);

               //CONTROL DE REPETIDO SOBRE LA RAMA
               boolean noRepetidoA = true;
               int p1 = this.camino.size() - 1;
               while((noRepetidoA)&&(p1>=0)){

                   int [][] elmAbiertos = this.camino.get(p1).getPosicion();
                   ultimoHIJO = tenerHijo.getHijos().size() - 1;
                   int [][] matrizHijo = tenerHijo.getHijos().get(ultimoHIJO).getPosicion();

                   boolean igual = true;
                   for(int i=0;i<8;i++){
                       for(int j=0;j<8;j++){
                          if(elmAbiertos[i][j] != matrizHijo[i][j]){
                            igual = false;
                          }
                       }
                   }

                  if(igual){

                    if(reglaAplicada == 8){
                        reglaAplicada = 1;
                    }else{
                        reglaAplicada = reglaAplicada + 1;
                    }

                    reglaAplicada = tenerHijo.obtenerHijo(reglaAplicada);
                    System.out.println("Encontro un hijo en abiertos, generamos uno nuevo");

                  }else{
                       p1 = p1 - 1;
                  }
               }

                //SE OBTUVO UN NODO VALIDO
                ultimoHIJO = tenerHijo.getHijos().size() - 1;
                int valorDelAcum;
                valorDelAcum = tenerHijo.getHijos().get(ultimoHIJO).getAcum20();
                
                //CONTROL DE RAMA INUTIL
                if(valorDelAcum>=30){
                    //debemos podar la rama
                    Nodo podado;
                    podado = tenerHijo.getHijos().get(ultimoHIJO);
                    this.explorados.add(podado);
                    System.out.println("Se agrego un nodo en explrados xq pasamos el 30");
                    if(reglaAplicada == 8){
                            reglaAplicada = 1;
                     }else{
                            reglaAplicada = reglaAplicada + 1;
                     }

                     reglaAplicada = tenerHijo.obtenerHijo(reglaAplicada);

                     ultimoHIJO = tenerHijo.getHijos().size() - 1;
                     tenerHijo.getHijos().get(ultimoHIJO).setAcum20(0);

                     //Aca hizo backtraking entonces resguardamos la profundidad alcanzada
                     this.resguardoExploracion = this.getProfundidadMaxima();
                     this.profundidadMaxima = this.profundidadMaxima - 1;
                    
                }

                ultimoHIJO = tenerHijo.getHijos().size() - 1;
                Nodo hijoNoRepetido;
                hijoNoRepetido = tenerHijo.getHijos().get(ultimoHIJO);
                hijoNoRepetido.setCosto(tenerHijo.getHijos().get(ultimoHIJO).getCosto());
                hijoNoRepetido.setAcum20(tenerHijo.getHijos().get(ultimoHIJO).getAcum20());
                this.camino.add(hijoNoRepetido);
                //SE AGREGA EL NUEVO NODO A ABIERTOS PORQUE CUMPLIO CON TODAS LAS CONDICIONES

                //Incrementamos el contador de produndidad
                this.profundidadMaxima = this.profundidadMaxima + 1;
                if(this.profundidadMaxima>this.resguardoExploracion){

                    this.resguardoExploracion = this.profundidadMaxima;

                }

                System.out.println("REGLA APLICADA:"+reglaAplicada);
                if(this.esEstadoFinal(hijoNoRepetido)){
                    nollegoAlFinal = false;
                    totalTiempo = 90000;
                    this.nivelSolucion = this.profundidadMaxima;
                    this.encontroSolucion = true;
                }

                reglaAplicada = 1;
                System.out.println("Hijo obtenido");
                hijoNoRepetido.mostrarValores();

                //Aca recalculamos el tiempo
                totalTiempo = System.currentTimeMillis() - tiempoInicio;
                this.setTiempoTotalBusqueda(totalTiempo);

                //VER SI HAY QUE PARAR LA EJECUCION POR DECISION DEL USUARIO
                if(this.parar){
                    nollegoAlFinal = false;
                    JOptionPane.showMessageDialog(null, "La Búsqueda ha sido detenida por decisión del usuario");
                    throw new ExcepcionParada("La busqueda ha sido detenida por el usuario");
                }

                if(this.esEstadoFinal(hijoNoRepetido)){
                    nollegoAlFinal = false;
                    totalTiempo = 90000;
                    this.nivelSolucion = this.profundidadMaxima;
                    this.encontroSolucion = true;
                }

            }

         }

    }
    //Metodo que devuelve true si el nodo recibido como parametro es el estado final
    public boolean esEstadoFinal(Nodo recibido){
        boolean es = false;
        int [][] valores;
        valores = new int[8][8];
        valores = recibido.getPosicion();
        int cant1 = 0;
        for(int i=0;i<8;i++){
            for(int j=0;j<8;j++){
                if(valores[i][j]==1){
                    cant1++;
                }
            }
        }

        if(cant1==0){
            es = true;
            this.costoFinal = recibido.getCosto();
        }
        return es;
    }


    //Getters  y Setters
    /**
     * @return the estadoInicial
     */
    public Nodo getEstadoInicial() {
        return estadoInicial;
    }

    /**
     * @param estadoInicial the estadoInicial to set
     */
    public void setEstadoInicial(Nodo estadoInicial) {
        this.estadoInicial = estadoInicial;
    }

    /**
     * @return the abiertos
     */
    public List<Nodo> getCamino() {
        return camino;
    }

    /**
     * @param abiertos the abiertos to set
     */
    public void setCamino(List<Nodo> camino) {
        this.setCamino(camino);
    }

    /**
     * @return the cerrados
     */
    public List<Nodo> getExplorados() {
        return explorados;
    }

    /**
     * @param cerrados the cerrados to set
     */
    public void setExplorados(List<Nodo> explorados) {
        this.setExplorados(explorados);
    }

    /**
     * @param abiertos the abiertos to set
     */
    

//Metodo que retorna el camino que llevo del estado inicial al estado final
public void devolverCamino(){
    System.out.println("Camino recorrido");
    for(int i=0;i<this.camino.size();i++){
        Nodo elm;
        elm = this.camino.get(i);
        int [][]matriz;
        matriz = new int[8][8];
        matriz = elm.getPosicion();
        for(int j=0;j<8;j++){
            for(int k=0;k<8;k++){
               System.out.print(matriz[j][k]);
            }
            System.out.println();
        }
        System.out.println();
    }

    System.out.println("Profundidad máxima alcanzada: "+this.profundidadMaxima);

}

//Metodos que retornan los valores de los parametros que vamos a mostrar como resultado

    /**
     * @return the profundidadMaxima
     */
    public int getProfundidadMaxima() {
        return profundidadMaxima;
    }

    /**
     * @param profundidadMaxima the profundidadMaxima to set
     */
    public void setProfundidadMaxima(int profundidadMaxima) {
        this.profundidadMaxima = profundidadMaxima;
    }

    /**
     * @return the resguardoExploracion
     */
    public int getResguardoProfundidad() {
        return resguardoExploracion;
    }

    /**
     * @param resguardoExploracion the resguardoExploracion to set
     */
    public void setResguardoProfundidad(int resguardoProfundidad) {
        this.resguardoExploracion = resguardoProfundidad;
    }

    /**
     * @return the cantidadNodosGenerados
     */
    public int getCantidadNodosGenerados() {
        return cantidadNodosGenerados;
    }

    /**
     * @param cantidadNodosGenerados the cantidadNodosGenerados to set
     */
    public void setCantidadNodosGenerados(int cantidadNodosGenerados) {
        this.cantidadNodosGenerados = cantidadNodosGenerados;
    }

    /**
     * @return the nivelSolucion
     */
    public int getNivelSolucion() {
        return nivelSolucion;
    }

    /**
     * @param nivelSolucion the nivelSolucion to set
     */
    public void setNivelSolucion(int nivelSolucion) {
        this.nivelSolucion = nivelSolucion;
    }

    /**
     * @return the encontroSolucion
     */
    public boolean isEncontroSolucion() {
        return encontroSolucion;
    }

    /**
     * @param encontroSolucion the encontroSolucion to set
     */
    public void setEncontroSolucion(boolean encontroSolucion) {
        this.encontroSolucion = encontroSolucion;
    }

    /**
     * @return the tiempoTotalBusqueda
     */
    public long getTiempoTotalBusqueda() {
        return tiempoTotalBusqueda;
    }

    /**
     * @param tiempoTotalBusqueda the tiempoTotalBusqueda to set
     */
    public void setTiempoTotalBusqueda(long tiempoTotalBusqueda) {
        this.tiempoTotalBusqueda = tiempoTotalBusqueda;
    }

    /**
     * @return the costoFinal
     */
    public int getCostoFinal() {
        return costoFinal;
    }

    /**
     * @param costoFinal the costoFinal to set
     */
    public void setCostoFinal(int costoFinal) {
        this.costoFinal = costoFinal;
    }

    /**
     * @return the parar
     */
    public boolean isParar() {
        return parar;
    }

    /**
     * @param parar the parar to set
     */
    public void setParar(boolean parar) {
        this.parar = parar;
    }

}
